home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part2 / 15118 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.7 KB
  1. Path: beta.nedernet.nl!usenet
  2. From: jos@and.nl (Jos A. Horsmeier)
  3. Newsgroups: comp.misc,comp.unix.programmer,comp.lang.c,comp.programming
  4. Subject: Re: Full Text Search Algorithms
  5. Date: 17 Apr 1996 10:19:47 GMT
  6. Organization: AND Operations Research B.V.
  7. Message-ID: <4l2gk3$lgd@beta.nedernet.nl>
  8. References: <3174436E.1A36@flashnet.it>
  9. NNTP-Posting-Host: klepzeiker.and.nl
  10. Mime-Version: 1.0
  11. Content-Type: Text/Plain; charset=ISO-8859-1
  12. X-Newsreader: WinVN 0.99.5
  13.  
  14. In article <3174436E.1A36@flashnet.it>, intarget@flashnet.it wrote:
  15.  
  16. |I need to build a full text search engine which can handle a large amount
  17. |of documents (about 300,000 plain text documents 3Kbytes long).
  18. |I tried with by implementing inverted lists of words with BTrees indexes, 
  19. |but the resulting software becomes too slow after the first 20,000 
  20. |documents. In addition, there's too much wasted space in the indexes.
  21. |
  22. |Can anybody suggest me a better algorithm and, if possible, tell me where 
  23. |can I find a technical description of it (possibly on the NET)?
  24.  
  25. Maybe the following approach helps you out:
  26.  
  27. - construct a list of unique words such that if a word is an element
  28.   of this list, then this word occurs at least once in at least one
  29.   document.
  30.  
  31. - for each word in the list above, construct a bit list such that
  32.   if a bit x in this list is set, then the word occurs in document
  33.   number x.
  34.  
  35. Words like 'the', 'and' etc. most likely have all their bits set
  36. in their bit lists and may be removed from the first list. Further
  37. reduction, i.e. compression of the bit lists, greatly reduces the
  38. total size of the database. Simple tricks like run length encoding
  39. come to mind ...
  40.  
  41. kind regards,
  42.  
  43. Jos aka jos@and.nl
  44. -- 
  45. Atnwgqkrl gy zit vgksr, ug qshiqwtzoeqs!
  46.  
  47.